package kyssion.introductionToAlgorithms.chapter_06;

public class Alorithms_6_003快速排序 {

    public static void main(String[] args) {
        new Alorithms_6_003快速排序().quickSort(new int[]{
                1,2,3,1
        },0,3);
    }

    public void quickSort(int[] arr, int start, int end) {
        if (start < end) {
            int midle = partition_s(arr, start, end);
            quickSort(arr, start, midle - 1);
            quickSort(arr, midle + 1, end);
        }
    }

    /**
     * 快速排序获得中间量方法1
     *
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private int partition_f(int[] arr, int start, int end) {
        int before = start - 1;
        int beforeNum = arr[end];
        while (start < end) {
            if (arr[start] <= beforeNum) {
                exchange(arr, ++before, start);
            }
            start++;
        }
        arr[before + 1] = beforeNum;
        return before + 1;
    }

    /**
     * 快速排序获得中间量方法2
     *
     * @param arr
     * @param start
     * @param end
     * @return
     */
    private int partition_s(int[] arr, int start, int end) {
        if(start>=end){
            return start;
        }
        int beforeNum = arr[start];
        while (start <= end) {
            while (start <= end && arr[end] >= beforeNum) {
                end--;
            }
            exchange(arr, start, end);
            while (start <= end && arr[start] <= beforeNum) {
                start++;
            }
            exchange(arr, start, end);
        }
        return start;
    }

    private void exchange(int[] arr, int a, int b) {
        int i = arr[a];
        arr[a] = arr[b];
        arr[b] = i;
    }
}
